Knowledge graphs provide rich semantic relations between entities. The recent availability of large-scale knowledge graphs (e.g., FACEBOOK's social graph) can provide a powerful resource for developers and computer programs to provide answers to user queries. However, large knowledge graphs may be very densely connected by, for example, tens of thousands of paths. Current solutions that follow all of these paths for a given query will return many incorrect answers because at least some of these paths will be irrelevant. Furthermore, this approach is costly and difficult to scale as knowledge graphs continue to increase in size and complexity.